package java_cup.runtime;

import java.util.Stack;

/**
 * This class implements a skeleton table driven LR parser. In general, LR
 * parsers are a form of bottom up shift-reduce parsers. Shift-reduce parsers
 * act by shifting input onto a parse stack until the Symbols matching the right
 * hand side of a production appear on the top of the stack. Once this occurs, a
 * reduce is performed. This involves removing the Symbols corresponding to the
 * right hand side of the production (the so called "handle") and replacing them
 * with the non-terminal from the left hand side of the production.
 * <p>
 * 
 * To control the decision of whether to shift or reduce at any given point, the
 * parser uses a state machine (the "viable prefix recognition machine" built by
 * the parser generator). The current state of the machine is placed on top of
 * the parse stack (stored as part of a Symbol object representing a terminal or
 * non terminal). The parse action table is consulted (using the current state
 * and the current lookahead Symbol as indexes) to determine whether to shift or
 * to reduce. When the parser shifts, it changes to a new state by pushing a new
 * Symbol (containing a new state) onto the stack. When the parser reduces, it
 * pops the handle (right hand side of a production) off the stack. This leaves
 * the parser in the state it was in before any of those Symbols were matched.
 * Next the reduce-goto table is consulted (using the new state and current
 * lookahead Symbol as indexes) to determine a new state to go to. The parser
 * then shifts to this goto state by pushing the left hand side Symbol of the
 * production (also containing the new state) onto the stack.
 * <p>
 * 
 * This class actually provides four LR parsers. The methods parse() and
 * debug_parse() provide two versions of the main parser (the only difference
 * being that debug_parse() emits debugging trace messages as it parses). In
 * addition to these main parsers, the error recovery mechanism uses two more.
 * One of these is used to simulate "parsing ahead" in the input without
 * carrying out actions (to verify that a potential error recovery has worked),
 * and the other is used to parse through buffered "parse ahead" input in order
 * to execute all actions and re-synchronize the actual parser configuration.
 * <p>
 * 
 * This is an abstract class which is normally filled out by a subclass
 * generated by the JavaCup parser generator. In addition to supplying the
 * actual parse tables, generated code also supplies methods which invoke
 * various pieces of user supplied code, provide access to certain special
 * Symbols (e.g., EOF and error), etc. Specifically, the following abstract
 * methods are normally supplied by generated code:
 * <dl compact>
 * <dt>short[][] production_table()
 * <dd>Provides a reference to the production table (indicating the index of the
 * left hand side non terminal and the length of the right hand side for each
 * production in the grammar).
 * <dt>short[][] action_table()
 * <dd>Provides a reference to the parse action table.
 * <dt>short[][] reduce_table()
 * <dd>Provides a reference to the reduce-goto table.
 * <dt>int start_state()
 * <dd>Indicates the index of the start state.
 * <dt>int start_production()
 * <dd>Indicates the index of the starting production.
 * <dt>int EOF_sym()
 * <dd>Indicates the index of the EOF Symbol.
 * <dt>int error_sym()
 * <dd>Indicates the index of the error Symbol.
 * <dt>Symbol do_action()
 * <dd>Executes a piece of user supplied action code. This always comes at the
 * point of a reduce in the parse, so this code also allocates and fills in the
 * left hand side non terminal Symbol object that is to be pushed onto the stack
 * for the reduce.
 * <dt>void init_actions()
 * <dd>Code to initialize a special object that encapsulates user supplied
 * actions (this object is used by do_action() to actually carry out the
 * actions).
 * </dl>
 * 
 * In addition to these routines that <i>must</i> be supplied by the generated
 * subclass there are also a series of routines that <i>may</i> be supplied.
 * These include:
 * <dl>
 * <dt>Symbol scan()
 * <dd>Used to get the next input Symbol from the scanner.
 * <dt>Scanner getScanner()
 * <dd>Used to provide a scanner for the default implementation of scan().
 * <dt>int error_sync_size()
 * <dd>This determines how many Symbols past the point of an error must be
 * parsed without error in order to consider a recovery to be valid. This
 * defaults to 3. Values less than 2 are not recommended.
 * <dt>void report_error(String message, Object info)
 * <dd>This method is called to report an error. The default implementation
 * simply prints a message to System.err and where the error occurred. This
 * method is often replaced in order to provide a more sophisticated error
 * reporting mechanism.
 * <dt>void report_fatal_error(String message, Object info)
 * <dd>This method is called when a fatal error that cannot be recovered from is
 * encountered. In the default implementation, it calls report_error() to emit a
 * message, then throws an exception.
 * <dt>void syntax_error(Symbol cur_token)
 * <dd>This method is called as soon as syntax error is detected (but before
 * recovery is attempted). In the default implementation it invokes:
 * report_error("Syntax error", null);
 * <dt>void unrecovered_syntax_error(Symbol cur_token)
 * <dd>This method is called if syntax error recovery fails. In the default
 * implementation it invokes:<br>
 * report_fatal_error("Couldn't repair and continue parse", null);
 * </dl>
 * 
 * @see java_cup.java_cup.runtime.Symbol
 * @see java_cup.java_cup.runtime.Symbol
 * @see java_cup.runtime.virtual_parse_stack
 * @version last updated: 7/3/96
 * @author Frank Flannery
 */

public abstract class lr_parser {

	/*-----------------------------------------------------------*/
	/*--- Constructor(s) ----------------------------------------*/
	/*-----------------------------------------------------------*/

	/** Simple constructor. */
	public lr_parser() {
		/* nothing to do here */
	}

	/** Constructor that sets the default scanner. [CSA/davidm] */
	public lr_parser(Scanner s) {
		this(); /* in case default constructor someday does something */
		setScanner(s);
	}

	/*-----------------------------------------------------------*/
	/*--- (Access to) Static (Class) Variables ------------------*/
	/*-----------------------------------------------------------*/

	/**
	 * The default number of Symbols after an error we much match to consider it
	 * recovered from.
	 */
	protected final static int _error_sync_size = 3;

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * The number of Symbols after an error we much match to consider it
	 * recovered from.
	 */
	protected int error_sync_size() {
		return _error_sync_size;
	}

	/*-----------------------------------------------------------*/
	/*--- (Access to) Instance Variables ------------------------*/
	/*-----------------------------------------------------------*/

	/**
	 * Table of production information (supplied by generated subclass). This
	 * table contains one entry per production and is indexed by the
	 * negative-encoded values (reduce actions) in the action_table. Each entry
	 * has two parts, the index of the non-terminal on the left hand side of the
	 * production, and the number of Symbols on the right hand side.
	 */
	public abstract short[][] production_table();

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * The action table (supplied by generated subclass). This table is indexed
	 * by state and terminal number indicating what action is to be taken when
	 * the parser is in the given state (i.e., the given state is on top of the
	 * stack) and the given terminal is next on the input. States are indexed
	 * using the first dimension, however, the entries for a given state are
	 * compacted and stored in adjacent index, value pairs which are searched
	 * for rather than accessed directly (see get_action()). The actions stored
	 * in the table will be either shifts, reduces, or errors. Shifts are
	 * encoded as positive values (one greater than the state shifted to).
	 * Reduces are encoded as negative values (one less than the production
	 * reduced by). Error entries are denoted by zero.
	 * 
	 * @see java_cup.java_cup.runtime.lr_parser#get_action
	 */
	public abstract short[][] action_table();

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * The reduce-goto table (supplied by generated subclass). This table is
	 * indexed by state and non-terminal number and contains state numbers.
	 * States are indexed using the first dimension, however, the entries for a
	 * given state are compacted and stored in adjacent index, value pairs which
	 * are searched for rather than accessed directly (see get_reduce()). When a
	 * reduce occurs, the handle (corresponding to the RHS of the matched
	 * production) is popped off the stack. The new top of stack indicates a
	 * state. This table is then indexed by that state and the LHS of the
	 * reducing production to indicate where to "shift" to.
	 * 
	 * @see java_cup.java_cup.runtime.lr_parser#get_reduce
	 */
	public abstract short[][] reduce_table();

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** The index of the start state (supplied by generated subclass). */
	public abstract int start_state();

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** The index of the start production (supplied by generated subclass). */
	public abstract int start_production();

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * The index of the end of file terminal Symbol (supplied by generated
	 * subclass).
	 */
	public abstract int EOF_sym();

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** The index of the special error Symbol (supplied by generated subclass). */
	public abstract int error_sym();

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Internal flag to indicate when parser should quit. */
	protected boolean _done_parsing = false;

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * This method is called to indicate that the parser should quit. This is
	 * normally called by an accept action, but can be used to cancel parsing
	 * early in other circumstances if desired.
	 */
	public void done_parsing() {
		_done_parsing = true;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */
	/*
	 * Global parse state shared by parse(), error recovery, and debugging
	 * routines
	 */
	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Indication of the index for top of stack (for use by actions). */
	protected int tos;

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** The current lookahead Symbol. */
	protected Symbol cur_token;

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** The parse stack itself. */
	protected Stack stack = new Stack();

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Direct reference to the production table. */
	protected short[][] production_tab;

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Direct reference to the action table. */
	protected short[][] action_tab;

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Direct reference to the reduce-goto table. */
	protected short[][] reduce_tab;

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * This is the scanner object used by the default implementation of scan()
	 * to get Symbols. To avoid name conflicts with existing code, this field is
	 * private. [CSA/davidm]
	 */
	private Scanner _scanner;

	/**
	 * Simple accessor method to set the default scanner.
	 */
	public void setScanner(Scanner s) {
		_scanner = s;
	}

	/**
	 * Simple accessor method to get the default scanner.
	 */
	public Scanner getScanner() {
		return _scanner;
	}

	/*-----------------------------------------------------------*/
	/*--- General Methods ---------------------------------------*/
	/*-----------------------------------------------------------*/

	/**
	 * Perform a bit of user supplied action code (supplied by generated
	 * subclass). Actions are indexed by an internal action number assigned at
	 * parser generation time.
	 * 
	 * @param act_num
	 *            the internal index of the action to be performed.
	 * @param parser
	 *            the parser object we are acting for.
	 * @param stack
	 *            the parse stack of that object.
	 * @param top
	 *            the index of the top element of the parse stack.
	 */
	public abstract Symbol do_action(int act_num, lr_parser parser,
			Stack stack, int top) throws java.lang.Exception;

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * User code for initialization inside the parser. Typically this
	 * initializes the scanner. This is called before the parser requests the
	 * first Symbol. Here this is just a placeholder for subclasses that might
	 * need this and we perform no action. This method is normally overridden by
	 * the generated code using this contents of the "init with" clause as its
	 * body.
	 */
	public void user_init() throws java.lang.Exception {
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Initialize the action object. This is called before the parser does any
	 * parse actions. This is filled in by generated code to create an object
	 * that encapsulates all action code.
	 */
	protected abstract void init_actions() throws java.lang.Exception;

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Get the next Symbol from the input (supplied by generated subclass). Once
	 * end of file has been reached, all subsequent calls to scan should return
	 * an EOF Symbol (which is Symbol number 0). By default this method returns
	 * getScanner().next_token(); this implementation can be overriden by the
	 * generated parser using the code declared in the "scan with" clause. Do
	 * not recycle objects; every call to scan() should return a fresh object.
	 */
	public Symbol scan() throws java.lang.Exception {
		Symbol sym = getScanner().next_token();
		return (sym != null) ? sym : new Symbol(EOF_sym());
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Report a fatal error. This method takes a message string and an
	 * additional object (to be used by specializations implemented in
	 * subclasses). Here in the base class a very simple implementation is
	 * provided which reports the error then throws an exception.
	 * 
	 * @param message
	 *            an error message.
	 * @param info
	 *            an extra object reserved for use by specialized subclasses.
	 */
	public void report_fatal_error(String message, Object info)
			throws java.lang.Exception {
		/* stop parsing (not really necessary since we throw an exception, but) */
		done_parsing();

		/* use the normal error message reporting to put out the message */
		report_error(message, info);

		/* throw an exception */
		throw new Exception("Can't recover from previous error(s)");
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Report a non fatal error (or warning). This method takes a message string
	 * and an additional object (to be used by specializations implemented in
	 * subclasses). Here in the base class a very simple implementation is
	 * provided which simply prints the message to System.err.
	 * 
	 * @param message
	 *            an error message.
	 * @param info
	 *            an extra object reserved for use by specialized subclasses.
	 */
	public void report_error(String message, Object info) {
		System.err.print(message);
		if (info instanceof Symbol)
			if (((Symbol) info).left != -1)
				System.err.println(" at character " + ((Symbol) info).left
						+ " of input");
			else
				System.err.println("");
		else
			System.err.println("");
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * This method is called when a syntax error has been detected and recovery
	 * is about to be invoked. Here in the base class we just emit a
	 * "Syntax error" error message.
	 * 
	 * @param cur_token
	 *            the current lookahead Symbol.
	 */
	public void syntax_error(Symbol cur_token) {
		report_error("Syntax error", cur_token);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * This method is called if it is determined that syntax error recovery has
	 * been unsuccessful. Here in the base class we report a fatal error.
	 * 
	 * @param cur_token
	 *            the current lookahead Symbol.
	 */
	public void unrecovered_syntax_error(Symbol cur_token)
			throws java.lang.Exception {
		report_fatal_error("Couldn't repair and continue parse", cur_token);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Fetch an action from the action table. The table is broken up into rows,
	 * one per state (rows are indexed directly by state number). Within each
	 * row, a list of index, value pairs are given (as sequential entries in the
	 * table), and the list is terminated by a default entry (denoted with a
	 * Symbol index of -1). To find the proper entry in a row we do a linear or
	 * binary search (depending on the size of the row).
	 * 
	 * @param state
	 *            the state index of the action being accessed.
	 * @param sym
	 *            the Symbol index of the action being accessed.
	 */
	protected final short get_action(int state, int sym) {
		short tag;
		int first, last, probe;
		short[] row = action_tab[state];

		/* linear search if we are < 10 entries */
		if (row.length < 20)
			for (probe = 0; probe < row.length; probe++) {
				/* is this entry labeled with our Symbol or the default? */
				tag = row[probe++];
				if (tag == sym || tag == -1) {
					/* return the next entry */
					return row[probe];
				}
			}
		/* otherwise binary search */
		else {
			first = 0;
			last = (row.length - 1) / 2 - 1; /* leave out trailing default entry */
			while (first <= last) {
				probe = (first + last) / 2;
				if (sym == row[probe * 2])
					return row[probe * 2 + 1];
				else if (sym > row[probe * 2])
					first = probe + 1;
				else
					last = probe - 1;
			}

			/* not found, use the default at the end */
			return row[row.length - 1];
		}

		/*
		 * shouldn't happened, but if we run off the end we return the default
		 * (error == 0)
		 */
		return 0;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Fetch a state from the reduce-goto table. The table is broken up into
	 * rows, one per state (rows are indexed directly by state number). Within
	 * each row, a list of index, value pairs are given (as sequential entries
	 * in the table), and the list is terminated by a default entry (denoted
	 * with a Symbol index of -1). To find the proper entry in a row we do a
	 * linear search.
	 * 
	 * @param state
	 *            the state index of the entry being accessed.
	 * @param sym
	 *            the Symbol index of the entry being accessed.
	 */
	protected final short get_reduce(int state, int sym) {
		short tag;
		short[] row = reduce_tab[state];

		/* if we have a null row we go with the default */
		if (row == null)
			return -1;

		for (int probe = 0; probe < row.length; probe++) {
			/* is this entry labeled with our Symbol or the default? */
			tag = row[probe++];
			if (tag == sym || tag == -1) {
				/* return the next entry */
				return row[probe];
			}
		}
		/* if we run off the end we return the default (error == -1) */
		return -1;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * This method provides the main parsing routine. It returns only when
	 * done_parsing() has been called (typically because the parser has
	 * accepted, or a fatal error has been reported). See the header
	 * documentation for the class regarding how shift/reduce parsers operate
	 * and how the various tables are used.
	 */
	public Symbol parse() throws java.lang.Exception {
		/* the current action code */
		int act;

		/* the Symbol/stack element returned by a reduce */
		Symbol lhs_sym = null;

		/* information about production being reduced with */
		short handle_size, lhs_sym_num;

		/* set up direct reference to tables to drive the parser */

		production_tab = production_table();
		action_tab = action_table();
		reduce_tab = reduce_table();

		/* initialize the action encapsulation object */
		init_actions();

		/* do user initialization */
		user_init();

		/* get the first token */
		cur_token = scan();

		/* push dummy Symbol with start state to get us underway */
		stack.removeAllElements();
		stack.push(new Symbol(0, start_state()));
		tos = 0;

		/* continue until we are told to stop */
		for (_done_parsing = false; !_done_parsing;) {
			/* Check current token for freshness. */
			if (cur_token.used_by_parser)
				throw new Error("Symbol recycling detected (fix your scanner).");

			/* current state is always on the top of the stack */

			/* look up action out of the current state with the current input */
			act = get_action(((Symbol) stack.peek()).parse_state, cur_token.sym);

			/* decode the action -- > 0 encodes shift */
			if (act > 0) {
				/* shift to the encoded state by pushing it on the stack */
				cur_token.parse_state = act - 1;
				cur_token.used_by_parser = true;
				stack.push(cur_token);
				tos++;

				/* advance to the next Symbol */
				cur_token = scan();
			}
			/* if its less than zero, then it encodes a reduce action */
			else if (act < 0) {
				/* perform the action for the reduce */
				lhs_sym = do_action((-act) - 1, this, stack, tos);

				/* look up information about the production */
				lhs_sym_num = production_tab[(-act) - 1][0];
				handle_size = production_tab[(-act) - 1][1];

				/* pop the handle off the stack */
				for (int i = 0; i < handle_size; i++) {
					stack.pop();
					tos--;
				}

				/* look up the state to go to from the one popped back to */
				act = get_reduce(((Symbol) stack.peek()).parse_state,
						lhs_sym_num);

				/* shift to that state */
				lhs_sym.parse_state = act;
				lhs_sym.used_by_parser = true;
				stack.push(lhs_sym);
				tos++;
			}
			/* finally if the entry is zero, we have an error */
			else if (act == 0) {
				/* call user syntax error reporting routine */
				syntax_error(cur_token);

				/* try to error recover */
				if (!error_recovery(false)) {
					/* if that fails give up with a fatal syntax error */
					unrecovered_syntax_error(cur_token);

					/* just in case that wasn't fatal enough, end parse */
					done_parsing();
				} else {
					lhs_sym = (Symbol) stack.peek();
				}
			}
		}
		return lhs_sym;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Write a debugging message to System.err for the debugging version of the
	 * parser.
	 * 
	 * @param mess
	 *            the text of the debugging message.
	 */
	public void debug_message(String mess) {
		System.err.println(mess);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Dump the parse stack for debugging purposes. */
	public void dump_stack() {
		if (stack == null) {
			debug_message("# Stack dump requested, but stack is null");
			return;
		}

		debug_message("============ Parse Stack Dump ============");

		/* dump the stack */
		for (int i = 0; i < stack.size(); i++) {
			debug_message("Symbol: " + ((Symbol) stack.elementAt(i)).sym
					+ " State: " + ((Symbol) stack.elementAt(i)).parse_state);
		}
		debug_message("==========================================");
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Do debug output for a reduce.
	 * 
	 * @param prod_num
	 *            the production we are reducing with.
	 * @param nt_num
	 *            the index of the LHS non terminal.
	 * @param rhs_size
	 *            the size of the RHS.
	 */
	public void debug_reduce(int prod_num, int nt_num, int rhs_size) {
		debug_message("# Reduce with prod #" + prod_num + " [NT=" + nt_num
				+ ", " + "SZ=" + rhs_size + "]");
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Do debug output for shift.
	 * 
	 * @param shift_tkn
	 *            the Symbol being shifted onto the stack.
	 */
	public void debug_shift(Symbol shift_tkn) {
		debug_message("# Shift under term #" + shift_tkn.sym + " to state #"
				+ shift_tkn.parse_state);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Do debug output for stack state. [CSA]
	 */
	public void debug_stack() {
		StringBuffer sb = new StringBuffer("## STACK:");
		for (int i = 0; i < stack.size(); i++) {
			Symbol s = (Symbol) stack.elementAt(i);
			sb.append(" <state " + s.parse_state + ", sym " + s.sym + ">");
			if ((i % 3) == 2 || (i == (stack.size() - 1))) {
				debug_message(sb.toString());
				sb = new StringBuffer("         ");
			}
		}
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Perform a parse with debugging output. This does exactly the same things
	 * as parse(), except that it calls debug_shift() and debug_reduce() when
	 * shift and reduce moves are taken by the parser and produces various other
	 * debugging messages.
	 */
	public Symbol debug_parse() throws java.lang.Exception {
		/* the current action code */
		int act;

		/* the Symbol/stack element returned by a reduce */
		Symbol lhs_sym = null;

		/* information about production being reduced with */
		short handle_size, lhs_sym_num;

		/* set up direct reference to tables to drive the parser */
		production_tab = production_table();
		action_tab = action_table();
		reduce_tab = reduce_table();

		debug_message("# Initializing parser");

		/* initialize the action encapsulation object */
		init_actions();

		/* do user initialization */
		user_init();

		/* the current Symbol */
		cur_token = scan();

		debug_message("# Current Symbol is #" + cur_token.sym);

		/* push dummy Symbol with start state to get us underway */
		stack.removeAllElements();
		stack.push(new Symbol(0, start_state()));
		tos = 0;

		/* continue until we are told to stop */
		for (_done_parsing = false; !_done_parsing;) {
			/* Check current token for freshness. */
			if (cur_token.used_by_parser)
				throw new Error("Symbol recycling detected (fix your scanner).");

			/* current state is always on the top of the stack */
			// debug_stack();

			/* look up action out of the current state with the current input */
			act = get_action(((Symbol) stack.peek()).parse_state, cur_token.sym);

			/* decode the action -- > 0 encodes shift */
			if (act > 0) {
				/* shift to the encoded state by pushing it on the stack */
				cur_token.parse_state = act - 1;
				cur_token.used_by_parser = true;
				debug_shift(cur_token);
				stack.push(cur_token);
				tos++;

				/* advance to the next Symbol */
				cur_token = scan();
				debug_message("# Current token is " + cur_token);
			}
			/* if its less than zero, then it encodes a reduce action */
			else if (act < 0) {
				/* perform the action for the reduce */
				lhs_sym = do_action((-act) - 1, this, stack, tos);

				/* look up information about the production */
				lhs_sym_num = production_tab[(-act) - 1][0];
				handle_size = production_tab[(-act) - 1][1];

				debug_reduce((-act) - 1, lhs_sym_num, handle_size);

				/* pop the handle off the stack */
				for (int i = 0; i < handle_size; i++) {
					stack.pop();
					tos--;
				}

				/* look up the state to go to from the one popped back to */
				act = get_reduce(((Symbol) stack.peek()).parse_state,
						lhs_sym_num);
				debug_message("# Reduce rule: top state "
						+ ((Symbol) stack.peek()).parse_state + ", lhs sym "
						+ lhs_sym_num + " -> state " + act);

				/* shift to that state */
				lhs_sym.parse_state = act;
				lhs_sym.used_by_parser = true;
				stack.push(lhs_sym);
				tos++;

				debug_message("# Goto state #" + act);
			}
			/* finally if the entry is zero, we have an error */
			else if (act == 0) {
				/* call user syntax error reporting routine */
				syntax_error(cur_token);

				/* try to error recover */
				if (!error_recovery(true)) {
					/* if that fails give up with a fatal syntax error */
					unrecovered_syntax_error(cur_token);

					/* just in case that wasn't fatal enough, end parse */
					done_parsing();
				} else {
					lhs_sym = (Symbol) stack.peek();
				}
			}
		}
		return lhs_sym;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */
	/* Error recovery code */
	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Attempt to recover from a syntax error. This returns false if recovery
	 * fails, true if it succeeds. Recovery happens in 4 steps. First we pop the
	 * parse stack down to a point at which we have a shift out of the top-most
	 * state on the error Symbol. This represents the initial error recovery
	 * configuration. If no such configuration is found, then we fail. Next a
	 * small number of "lookahead" or "parse ahead" Symbols are read into a
	 * buffer. The size of this buffer is determined by error_sync_size() and
	 * determines how many Symbols beyond the error must be matched to consider
	 * the recovery a success. Next, we begin to discard Symbols in attempt to
	 * get past the point of error to a point where we can continue parsing.
	 * After each Symbol, we attempt to "parse ahead" though the buffered
	 * lookahead Symbols. The "parse ahead" process simulates that actual parse,
	 * but does not modify the real parser's configuration, nor execute any
	 * actions. If we can parse all the stored Symbols without error, then the
	 * recovery is considered a success. Once a successful recovery point is
	 * determined, we do an actual parse over the stored input -- modifying the
	 * real parse configuration and executing all actions. Finally, we return
	 * the the normal parser to continue with the overall parse.
	 * 
	 * @param debug
	 *            should we produce debugging messages as we parse.
	 */
	protected boolean error_recovery(boolean debug) throws java.lang.Exception {
		if (debug)
			debug_message("# Attempting error recovery");

		/*
		 * first pop the stack back into a state that can shift on error and do
		 * that shift (if that fails, we fail)
		 */
		if (!find_recovery_config(debug)) {
			if (debug)
				debug_message("# Error recovery fails");
			return false;
		}

		/* read ahead to create lookahead we can parse multiple times */
		read_lookahead();

		/* repeatedly try to parse forward until we make it the required dist */
		for (;;) {
			/* try to parse forward, if it makes it, bail out of loop */
			if (debug)
				debug_message("# Trying to parse ahead");
			if (try_parse_ahead(debug)) {
				break;
			}

			/* if we are now at EOF, we have failed */
			if (lookahead[0].sym == EOF_sym()) {
				if (debug)
					debug_message("# Error recovery fails at EOF");
				return false;
			}

			/* otherwise, we consume another Symbol and try again */
			// BUG FIX by Bruce Hutton
			// Computer Science Department, University of Auckland,
			// Auckland, New Zealand.
			// It is the first token that is being consumed, not the one
			// we were up to parsing
			if (debug)
				debug_message("# Consuming Symbol #" + lookahead[0].sym);
			restart_lookahead();
		}

		/* we have consumed to a point where we can parse forward */
		if (debug)
			debug_message("# Parse-ahead ok, going back to normal parse");

		/* do the real parse (including actions) across the lookahead */
		parse_lookahead(debug);

		/* we have success */
		return true;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Determine if we can shift under the special error Symbol out of the state
	 * currently on the top of the (real) parse stack.
	 */
	protected boolean shift_under_error() {
		/* is there a shift under error Symbol */
		return get_action(((Symbol) stack.peek()).parse_state, error_sym()) > 0;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Put the (real) parse stack into error recovery configuration by popping
	 * the stack down to a state that can shift on the special error Symbol,
	 * then doing the shift. If no suitable state exists on the stack we return
	 * false
	 * 
	 * @param debug
	 *            should we produce debugging messages as we parse.
	 */
	protected boolean find_recovery_config(boolean debug) {
		Symbol error_token;
		int act;

		if (debug)
			debug_message("# Finding recovery state on stack");

		/* Remember the right-position of the top symbol on the stack */
		int right_pos = ((Symbol) stack.peek()).right;
		int left_pos = ((Symbol) stack.peek()).left;

		/* pop down until we can shift under error Symbol */
		while (!shift_under_error()) {
			/* pop the stack */
			if (debug)
				debug_message("# Pop stack by one, state was # "
						+ ((Symbol) stack.peek()).parse_state);
			left_pos = ((Symbol) stack.pop()).left;
			tos--;

			/* if we have hit bottom, we fail */
			if (stack.empty()) {
				if (debug)
					debug_message("# No recovery state found on stack");
				return false;
			}
		}

		/* state on top of the stack can shift under error, find the shift */
		act = get_action(((Symbol) stack.peek()).parse_state, error_sym());
		if (debug) {
			debug_message("# Recover state found (#"
					+ ((Symbol) stack.peek()).parse_state + ")");
			debug_message("# Shifting on error to state #" + (act - 1));
		}

		/* build and shift a special error Symbol */
		error_token = new Symbol(error_sym(), left_pos, right_pos);
		error_token.parse_state = act - 1;
		error_token.used_by_parser = true;
		stack.push(error_token);
		tos++;

		return true;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Lookahead Symbols used for attempting error recovery "parse aheads". */
	protected Symbol lookahead[];

	/** Position in lookahead input buffer used for "parse ahead". */
	protected int lookahead_pos;

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Read from input to establish our buffer of "parse ahead" lookahead
	 * Symbols.
	 */
	protected void read_lookahead() throws java.lang.Exception {
		/* create the lookahead array */
		lookahead = new Symbol[error_sync_size()];

		/* fill in the array */
		for (int i = 0; i < error_sync_size(); i++) {
			lookahead[i] = cur_token;
			cur_token = scan();
		}

		/* start at the beginning */
		lookahead_pos = 0;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Return the current lookahead in our error "parse ahead" buffer. */
	protected Symbol cur_err_token() {
		return lookahead[lookahead_pos];
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Advance to next "parse ahead" input Symbol. Return true if we have input
	 * to advance to, false otherwise.
	 */
	protected boolean advance_lookahead() {
		/* advance the input location */
		lookahead_pos++;

		/* return true if we didn't go off the end */
		return lookahead_pos < error_sync_size();
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Reset the parse ahead input to one Symbol past where we started error
	 * recovery (this consumes one new Symbol from the real input).
	 */
	protected void restart_lookahead() throws java.lang.Exception {
		/* move all the existing input over */
		for (int i = 1; i < error_sync_size(); i++)
			lookahead[i - 1] = lookahead[i];

		/* read a new Symbol into the last spot */
		// BUG Fix by Bruce Hutton
		// Computer Science Department, University of Auckland,
		// Auckland, New Zealand. [applied 5-sep-1999 by csa]
		// The following two lines were out of order!!
		lookahead[error_sync_size() - 1] = cur_token;
		cur_token = scan();

		/* reset our internal position marker */
		lookahead_pos = 0;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Do a simulated parse forward (a "parse ahead") from the current stack
	 * configuration using stored lookahead input and a virtual parse stack.
	 * Return true if we make it all the way through the stored lookahead input
	 * without error. This basically simulates the action of parse() using only
	 * our saved "parse ahead" input, and not executing any actions.
	 * 
	 * @param debug
	 *            should we produce debugging messages as we parse.
	 */
	protected boolean try_parse_ahead(boolean debug) throws java.lang.Exception {
		int act;
		short lhs, rhs_size;

		/* create a virtual stack from the real parse stack */
		virtual_parse_stack vstack = new virtual_parse_stack(stack);

		/* parse until we fail or get past the lookahead input */
		for (;;) {
			/* look up the action from the current state (on top of stack) */
			act = get_action(vstack.top(), cur_err_token().sym);

			/* if its an error, we fail */
			if (act == 0)
				return false;

			/* > 0 encodes a shift */
			if (act > 0) {
				/* push the new state on the stack */
				vstack.push(act - 1);

				if (debug)
					debug_message("# Parse-ahead shifts Symbol #"
							+ cur_err_token().sym + " into state #" + (act - 1));

				/* advance simulated input, if we run off the end, we are done */
				if (!advance_lookahead())
					return true;
			}
			/* < 0 encodes a reduce */
			else {
				/* if this is a reduce with the start production we are done */
				if ((-act) - 1 == start_production()) {
					if (debug)
						debug_message("# Parse-ahead accepts");
					return true;
				}

				/* get the lhs Symbol and the rhs size */
				lhs = production_tab[(-act) - 1][0];
				rhs_size = production_tab[(-act) - 1][1];

				/* pop handle off the stack */
				for (int i = 0; i < rhs_size; i++)
					vstack.pop();

				if (debug)
					debug_message("# Parse-ahead reduces: handle size = "
							+ rhs_size + " lhs = #" + lhs + " from state #"
							+ vstack.top());

				/* look up goto and push it onto the stack */
				vstack.push(get_reduce(vstack.top(), lhs));
				if (debug)
					debug_message("# Goto state #" + vstack.top());
			}
		}
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Parse forward using stored lookahead Symbols. In this case we have
	 * already verified that parsing will make it through the stored lookahead
	 * Symbols and we are now getting back to the point at which we can hand
	 * control back to the normal parser. Consequently, this version of the
	 * parser performs all actions and modifies the real parse configuration.
	 * This returns once we have consumed all the stored input or we accept.
	 * 
	 * @param debug
	 *            should we produce debugging messages as we parse.
	 */
	protected void parse_lookahead(boolean debug) throws java.lang.Exception {
		/* the current action code */
		int act;

		/* the Symbol/stack element returned by a reduce */
		Symbol lhs_sym = null;

		/* information about production being reduced with */
		short handle_size, lhs_sym_num;

		/* restart the saved input at the beginning */
		lookahead_pos = 0;

		if (debug) {
			debug_message("# Reparsing saved input with actions");
			debug_message("# Current Symbol is #" + cur_err_token().sym);
			debug_message("# Current state is #"
					+ ((Symbol) stack.peek()).parse_state);
		}

		/* continue until we accept or have read all lookahead input */
		while (!_done_parsing) {
			/* current state is always on the top of the stack */

			/* look up action out of the current state with the current input */
			act = get_action(((Symbol) stack.peek()).parse_state,
					cur_err_token().sym);

			/* decode the action -- > 0 encodes shift */
			if (act > 0) {
				/* shift to the encoded state by pushing it on the stack */
				cur_err_token().parse_state = act - 1;
				cur_err_token().used_by_parser = true;
				if (debug)
					debug_shift(cur_err_token());
				stack.push(cur_err_token());
				tos++;

				/* advance to the next Symbol, if there is none, we are done */
				if (!advance_lookahead()) {
					if (debug)
						debug_message("# Completed reparse");

					/* scan next Symbol so we can continue parse */
					// BUGFIX by Chris Harris <ckharris@ucsd.edu>:
					// correct a one-off error by commenting out
					// this next line.
					/* cur_token = scan(); */

					/* go back to normal parser */
					return;
				}

				if (debug)
					debug_message("# Current Symbol is #" + cur_err_token().sym);
			}
			/* if its less than zero, then it encodes a reduce action */
			else if (act < 0) {
				/* perform the action for the reduce */
				lhs_sym = do_action((-act) - 1, this, stack, tos);

				/* look up information about the production */
				lhs_sym_num = production_tab[(-act) - 1][0];
				handle_size = production_tab[(-act) - 1][1];

				if (debug)
					debug_reduce((-act) - 1, lhs_sym_num, handle_size);

				/* pop the handle off the stack */
				for (int i = 0; i < handle_size; i++) {
					stack.pop();
					tos--;
				}

				/* look up the state to go to from the one popped back to */
				act = get_reduce(((Symbol) stack.peek()).parse_state,
						lhs_sym_num);

				/* shift to that state */
				lhs_sym.parse_state = act;
				lhs_sym.used_by_parser = true;
				stack.push(lhs_sym);
				tos++;

				if (debug)
					debug_message("# Goto state #" + act);

			}
			/*
			 * finally if the entry is zero, we have an error (shouldn't happen
			 * here, but...)
			 */
			else if (act == 0) {
				report_fatal_error("Syntax error", lhs_sym);
				return;
			}
		}

	}

	/*-----------------------------------------------------------*/

	/** Utility function: unpacks parse tables from strings */
	protected static short[][] unpackFromStrings(String[] sa) {
		// Concatanate initialization strings.
		StringBuffer sb = new StringBuffer(sa[0]);
		for (int i = 1; i < sa.length; i++)
			sb.append(sa[i]);
		int n = 0; // location in initialization string
		int size1 = (((int) sb.charAt(n)) << 16) | ((int) sb.charAt(n + 1));
		n += 2;
		short[][] result = new short[size1][];
		for (int i = 0; i < size1; i++) {
			int size2 = (((int) sb.charAt(n)) << 16) | ((int) sb.charAt(n + 1));
			n += 2;
			result[i] = new short[size2];
			for (int j = 0; j < size2; j++)
				result[i][j] = (short) (sb.charAt(n++) - 2);
		}
		return result;
	}
}
